Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,

reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

For example,

Given {1,2,3,4}, reorder it to {1,4,2,3}.

Solution:

  1. /**
  2.  * Definition for singly-linked list.
  3.  * class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) {
  7.  *         val = x;
  8.  *         next = null;
  9.  *     }
  10.  * }
  11.  */
  12. public class Solution {
  13.   public void reorderList(ListNode head) {
  14.     if (head == null || head.next == null)
  15.       return;
  17.     // step 1. cut the list to two halves
  18.     // prev will be the tail of 1st half
  19.     // slow will be the head of 2nd half
  20.     ListNode prev = null, slow = head, fast = head, l1 = head;
  22.     while (fast != null && fast.next != null) {
  23.       prev = slow;
  24.       slow = slow.next;
  25.       fast = fast.next.next;
  26.     }
  28.     prev.next = null;
  30.     // step 2. reverse the 2nd half
  31.     ListNode l2 = reverse(slow);
  33.     // step 3. merge the two halves
  34.     merge(l1, l2);
  35.   }
  37.   ListNode reverse(ListNode head) {
  38.     ListNode prev = null, curr = head, next = null;
  40.     while (curr != null) {
  41.       next = curr.next;
  42.       curr.next = prev;
  43.       prev = curr;
  44.       curr = next;
  45.     }
  47.     return prev;
  48.   }
  50.   void merge(ListNode l1, ListNode l2) {
  51.     while (l1 != null) {
  52.       ListNode n1 = l1.next, n2 = l2.next;
  53.       l1.next = l2;
  55.       if (n1 == null)
  56.         break;
  58.       l2.next = n1;
  59.       l1 = n1;
  60.       l2 = n2;
  61.     }
  62.   }
  63. }